package com.sort;

/**
 * 归并排序
 * @author dingnate
 */
public class SortMerge {

	public static void merge(int[] array, int p, int q, int r) {
		int i, j, k, n1, n2;
		n1 = q - p + 1;
		n2 = r - q;
		int[] left = new int[n1];
		int[] rigth = new int[n2];
		for (i = 0, k = p; i < n1; i++, k++){
			left[i] = array[k];
		}
		for (i = 0, k = q + 1; i < n2; i++, k++){
			rigth[i] = array[k];
		}
		for (k = p, i = 0, j = 0; i < n1 && j < n2; k++) {
			if (left[i] < rigth[j]) {
				array[k] = left[i];
				i++;
			} else {
				array[k] = rigth[j];
				j++;
			}
		}
		if (i < n1) {
			for (j = i; j < n1; j++, k++){
				array[k] = left[j];
			}
		}
		if (j < n2) {
			for (i = j; i < n2; i++, k++){
				array[k] = rigth[i];
			}
		}
	}

	public static void mergeSort(int[] array, int p, int r) {
		if (p < r) {
			int q = (p + r) / 2;
			mergeSort(array, p, q);
			mergeSort(array, q + 1, r);
			merge(array, p, q, r);
		}
	}

	public static void main(String[] args) {
		int i = 0;
		int a[] = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };
		int len = a.length;
		mergeSort(a, 0, len - 1);
		for (i = 0; i < len; i++){
			System.out.print(a[i] + " ");
		}
	}
}